/* 300. 最长递增子序列 */
/**
 * @param {number[]} nums
 * @return {number}
 */

/* dp[i]从下标0开始的最长子序列长度 */
var lengthOfLIS = function (nums) {
    const dp = new Array(nums.length).fill(1)
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            /* 找到比i小的元素找到下一个就让当前序列的最长子序列长度加1 */
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }
    return Math.max(...dp)
};
/* 二分查找 */
var lengthOfLIS = function (nums) {
    const top = []
    /* 牌的堆数 */
    let piles = 0
    for (let i = 0; i < nums.length; i++) {
        let poker = nums[i]
        //左堆和最右堆进行二分搜索，因为堆顶是有序的，最终找到该牌要插入的堆
        let left = 0, right = piles
        while (left < right) {
            let mid = left + ((right - left) >> 1)
            if (top[mid] < poker) {
                left = mid + 1
            } else {
                right = mid
            }
        }
        /* 没有找到合适的牌堆 新建一堆 */
        if (left == piles) piles++
        /* 把这张牌放到堆顶 */
        top[left] = poker
    }

    return piles
}
lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])